package 剑指offer;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhangmin
 * @create 2021-11-27 10:49
 * 排序
 */
public class day17_40_41 {

    /**===========================================================================================================================
     * 剑指 Offer 40. 最小的k个数
     * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     * 1、排序
     * 2、快速查找
     * */
    public int[] getLeastNumbers1(int[] arr, int k) {
        Arrays.sort(arr);
        int[] res=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=arr[i];
        }
        return res;
    }
    //2、快排
    int partition(int[] arr,int left,int right){
        int v=arr[left];
        int i=left+1,j=right;
        while (true){
            while (i<=right&&arr[i]<v) i++;
            while (j>=left&&arr[j]>v)j--;
            if (i>=j)break;
            int t=arr[i];
            arr[i]=arr[j];
            arr[j]=t;
        }
        arr[left]=arr[j];
        arr[j]=v;
        return j;
    }
    int[] quickSearch(int[] arr,int left,int right,int k){
        int j=partition(arr,left,right);
        if (j==k){
            return Arrays.copyOf(arr,j+1);
        }
        return j>k?quickSearch(arr,left,j-1,k):quickSearch(arr,j+1,right,k);
    }
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k==0||arr.length==0){
            return new int[0];
        }
        return quickSearch(arr,0,arr.length-1,k-1);
    }

    /**===========================================================================================================================
     * 剑指 Offer 41. 数据流中的中位数
     * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
     * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
     *
     * 使用两个优先队列（从大到小），一个用于做小顶堆，另一个用作大顶堆
     * 在添加元素时，要维护两个堆中元素的个数查最大为1，
     *   --在small中的元素个数多时，需要向large中添加，先将他添加到small中，然后将samll中的对顶元素取出来放到large中
     *   --在large中的元素个数多时，同理需要向small中添加，先向large中添加，然后将large的堆顶拿出来放到samll中
     * */
    class MedianFinder {
        //使用两个优先队列实现
        PriorityQueue<Integer> large;
        PriorityQueue<Integer> small;

        /** initialize your data structure here. */
        public MedianFinder() {
            // 小顶堆:存放前一半的元素
            large=new PriorityQueue<>();
            // 大顶堆：存放后一半的元素（小的一半元素)
            small=new PriorityQueue<>((o1, o2) -> o2-o1);
        }

        public void addNum(int num) {
            if (small.size()<=large.size()){
                //需要向small中添加
                large.offer(num);
                small.offer(large.poll());
            }else {
                small.offer(num);
                large.offer(small.poll());
            }
        }
        //返回目前所有元素的中位数。
        public double findMedian() {
            // 如果元素不一样多，多的那个堆的堆顶元素就是中位数
            if (small.size()>large.size()){
                return small.peek();
            }else if (small.size()<large.size()){
                return large.size();
            }
            // 如果元素一样多，两个堆堆顶元素的平均数是中位数
            return (small.peek()+large.peek())/2.0;
        }
    }
}
